package JZ_Offer.algorithm.other.数组;

/**
 * 构建乘积数组
 *
 * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
 * （注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
 */
public class JZ66_构建乘积数组 {

    /**
     * 可以把B[i]=A[0]A[1]....A[i-1]A[i+1]....A[n-1]。看成A[0]A[1].....A[i-1]和A[i+1].....A[n-2]A[n-1]两部分的乘积。
     * 两次循环 第一次循环计算前半部分 并将结果放入B中相应位置，第二次循环计算后半部分并和B中已经计算好的前半部分相乘
     */
    private static int[] multiply(int[] A) {
        int length = A.length;
        int[] B = new int[length];
        B[0] = 1;

        // 第一遍计算 0 - i-1
        int count = A[0];
        for (int i = 1; i < length; i++) {
            B[i] = count;
            count *= A[i];
        }

        // 第二遍计算 i+1 - n
        count = A[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            B[i] *= count;
            count *= A[i];
        }
        return B;
    }

    public static void main(String[] args) {
        int[] A = new int[]{1, 2, 3};
        int[] multiply = multiply(A);
        System.out.println();
    }
}
